今天第一次打模拟赛题解啦啦啦~ ~ ~ 关键是这一次题目比较水

Streaming#6 NOIP模拟赛Day2

T1: 九九归一

题意简述

若满足 $a^x\equiv 1(mod\ n)$ 且$x=\phi (n)$ ，并不存在更小的x满足此等式

给定$n$,共$m$个数，若满足上述条件输出1，不满足输出0。

题解

事实上这题的精髓在于求phi，但由于偷懒看了之前的代码就。。。

首先因为数据水，所以直接把n因数分解一个个判断就可以。

正解可以考虑质因数分解，每次判断
$$
x^{\frac{\phi(n)}{p_i}}\equiv 1 (mod\ n)
$$
就可以，因为质因数很少，每次出去其中一个质因数之后的数就包含了其他的质因子，如果大的数都不满足，小的也不会满足，因此可以判断。

但我好像正解打挂了就放个暴力，反正是混过了的

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e7+110;
int n,phi[N],prime[N],fact[N],cnt,q;
bool flag[N];
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
void init(int m)
{
    flag[1]=1;
    phi[1]=1;
    for(int i=2;i<=m;i++)
    {
        if(!flag[i])
        {
            prime[++prime[0]]=i;
            phi[i]=i-1;
        }
         for(int j=1;j<=prime[0]&&prime[j]*i<=m;j++)
         {
             flag[i*prime[j]]=1;
             phi[i*prime[j]]=phi[i]*(prime[j]-1);
             if(i%prime[j]==0)
             {
                 phi[i*prime[j]]=phi[i]*prime[j];
                 break;
             }
         }
    }
   int x=phi[m];
   for(int i=2;i<=sqrt(x);i++)
    if(x%i==0)
      fact[++cnt]=i;
}
int ksm(int x,int y,int mod)
{
    int sum=1;
    while(y)
    {
        if(y&1)sum=sum*x%mod;
        x=x*x%mod;
        y/=2;
    }
    return sum;
}
bool check(int x)
{
    for(int i=1;i<=cnt;i++)
    {
        if(ksm(x,fact[i],n)%n==1||ksm(x,phi[n]/fact[i],n)%n==1)return 0;
    }
    return 1;
}
main()
{
    n=read();q=read();
    init(n);
    for(int i=1;i<=q;i++)
    {
        int x;
        x=read();
        if(x==1||x==0){putchar('0');continue;}
        if(ksm(x,n,n)%n==1){putchar('0');continue;}
        if(check(x))putchar('1');
        else putchar('0');
    }
    return 0;
}

T2: LCA的统计

题意简述

给一定一棵树，求出以下式子的和对mod 1e9+7
$$
\sum_{i=1}^n \sum_{j=1}^n W_i W_j W_{lca(i,j)}
$$

题解

这个题就很水，有很多中做法，有$dfs$，树形$dp$，因为我$dp$学的不好就只打了一个暴力$dfs$

很好想，先加上所有自己和自己组合的点对。

然后在每次$dfs$开始的时候先算以自己为$lca$，也就是子树的答案和。这是求x到每个$son[x]$的权值之积，再考虑求子树之间的自由组合，相当于路径拼接一下的，也是把两边的权值积乘起来就行，很好理解。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+110;
const int mod=1e9+7;
int n,m,head[N],siz[N],deep[N],top[N],fa[N],cnt,w[N],son[N];
int sum1,ans;
long long mult(long long x,long long y)//其实不用龟速乘
{
    long long sum=0;
    while(y)
    {
        if(y%2)
            sum=(sum+x)%mod;
        x=(x+x)%mod;
        y=y/2;

    }
    return sum;
} 
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
struct node
{
    int nt,to;
}edge[N*2];
void add(int x,int y)
{
    edge[++cnt]=(node){head[x],y};head[x]=cnt;
    edge[++cnt]=(node){head[y],x};head[y]=cnt;
}
void dfs(int x,int fa1,int d)
{
    deep[x]=d;fa[x]=fa1;siz[x]=1;son[x]=w[x];
    for(int i=head[x];i;i=edge[i].nt)
    {
        int v=edge[i].to;
        if(v==fa1)continue;
        dfs(v,x,d+1);
        siz[x]+=siz[v];
        son[x]=(son[x]+son[v])%mod;
    }
}
void DFS(int x)
{
    if(siz[x]==1)return ;
    sum1=(sum1+mult(mult(w[x],w[x]),(son[x]-w[x]+mod))*2%mod)%mod;//有减号的地方一定记得+mod
    for(int i=head[x];i;i=edge[i].nt)
    {
        int v=edge[i].to;
        if(v==fa[x])continue;
        sum1=(sum1+mult(mult(w[x],(son[v])),(son[x]-son[v]-w[x]+mod))%mod)%mod;
        DFS(v);
    }
}
main()
{
    n=read();w[1]=read();ans+=mult(mult(w[1],w[1]),w[1]);
    for(int i=2;i<=n;i++)
    {
        fa[i]=read();w[i]=read();
        add(i,fa[i]);
        ans=(ans+mult(mult(w[i],w[i]),w[i]))%mod;
    }
    dfs(1,0,1);
    DFS(1);
    ans=(ans+sum1)%mod;
    printf("%lld",ans%mod);
    return 0;
}

T3: 四驱兄弟

题意简述

给定一些字符串，每个字符串对应一个点，给定一些边，求有哪些边相连之后不会出现环。、

（实际上题目描述非常难懂。。。。）

题解

实际上此题读题有些费劲，但看懂了就是一道kruskal裸题。

首先用hash或map处理一下字符串。然后按边权排序，用并查集判环。

每次加边前判定一下$findf(x)$ 是否等于$findf(y)$，就行。。。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+110;
const int INF=(1<<30);
int n,m,head[N],id,fa[N],minn=(1<<30),ans[N],cnt;
map<string,int>name;
string s,t;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
struct node
{
    int w,u,v;
    bool operator < (const node &a)const
    {
        return w<a.w;
    }
}edge[N*2];

int findf(int x)
{
    if(x==fa[x])return x;
    else return fa[x]=findf(fa[x]);
}
void Kruskal()
{
    int cnt=0;
    for(int i=1;i<=n;i++)
    {
        int fx=findf(edge[i].u);
        int fy=findf(edge[i].v);
        if(fx==fy){continue;}
        printf("%lld\n",edge[i].w);
        fa[fx]=fy;
        cnt++;
    }
    for(int i=cnt+1;i<=m;i++)printf("INF\n");
}
main()
{
    m=read();n=read();
    for(int i=1;i<=n;i++)
    {
        edge[i].w=read();
        cin>>s>>t;
        if(!name[s])name[s]=++id;
        if(!name[t])name[t]=++id;
        edge[i].u=name[s],edge[i].v=name[t];

    }
    for(int i=1;i<=id;i++)fa[i]=i;
    sort(edge+1,edge+1+n);
    Kruskal();
    return 0;
}